package offerbook;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created at 2019/10/26 0026 下午 11:12
 * topK问题
 *
 * 方式1：排序，时间O(nlogn)
 * 方式2：基于堆,时间O(nlogk) ， 适用于海量数据
 * 方式3：BTPRF或 基于经典快排的partition
 * 时间O(n),空间：如果不允许改变原数组则需要拷贝一份是O(n)，允许改变则O(1)
 */
public class Code30_TopK {

    //方式1：利用系统的排序即可

    //方式2：构造大根堆
    public static ArrayList<Integer> getMinK1(int [] arr, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(arr == null || arr.length == 0 || k < 1 || k > arr.length ){
            return list;
        }
        int[] res = new MinK(arr,k).getK();
        for (int i = 0; i < res.length; i++) {
            list.add(res[i]);
        }
        return list;
    }
    private static class MinK{
        //大根堆比较规则
        private static class MyComparator implements Comparator<Integer>{
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        }
        private PriorityQueue<Integer> queue;

        private int k;

        public MinK(int k) {
            this.queue = new PriorityQueue<>(new MyComparator());
            this.k = k;
        }

        public MinK(int []arr,int k){
            this.queue = new PriorityQueue<>(new MyComparator());
            this.k = k;
            for (int i = 0; i < arr.length; i++) {
                put(arr[i]);
            }
        }

        public void put(int e){
            if(queue.size() < k){
                queue.add(e);
                return;
            }
            //否则与堆顶比较,如果比最大的还小，那么可以入小根堆
            if(e < queue.peek()){
                queue.poll();
                queue.add(e);
            }
        }

        public int[] getK(){
            int []res = new int[k];

            for (int i = 0; i < k; i++) {
                res[i] = queue.poll();
            }
            return res;
        }
    }

    //方式3：BFPRT或基于快排的partition

    public static  ArrayList<Integer> getMinK2(int[]arr , int k){
        ArrayList<Integer> list = new ArrayList<>();
        if(arr == null || arr.length == 0 || k < 1 || k > arr.length ){
            return list;
        }
        int[] help = Arrays.copyOf(arr, arr.length);

        //如果是求topK，第K大就是第n-k+1小，那么传参是n-k 索引即可
        int kValue = select(help,k-1);

        for (int i = 0; i < arr.length; i++) {
            //如果是求topK，换成大于号
            if(arr[i] < kValue){
                list.add(arr[i]);
            }
        }
        while (list.size() < k){
            list.add(kValue);
        }
        return list;
    }

    private static int select(int[] arr,int index) {
        int start = 0;
        int end = arr.length - 1;
        //BFPRT  这里的target改变即可，其他的不用改变
        int target = getMedianOfMedians(arr,start,end);
//        int target = arr[(int) (Math.random()*(end - start + 1)+start)];
        int[] range = partition(arr, start, end,target);

        while (!(index>=range[0] && index <= range[1])){
            if(index < range[0]){
                end = range[0] -1;
            }else if(index > range[1]){
                start = range[1] + 1;
            }
            target = getMedianOfMedians(arr,start,end);
            //target = arr[(int) (Math.random()*(end - start + 1)+start)];
            range = partition(arr,start,end,target);
        }
        return arr[index];
    }



    private static int[] partition(int[] arr, int begin, int end,int target) {
        int less = begin - 1;
        int cur = begin;
        int more = end + 1;
        while (cur != more) {
            if (arr[cur] < target) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > target) {
                swap(arr, cur, --more);
            } else {
                cur++;
            }
        }
        int[] range = new int[2];
        range[0] = less + 1;
        range[1] = more - 1;
        return range;
    }

    /*======================BFPRT===========================*/
    private static int getMedianOfMedians(int[] arr, int start, int end) {
        int offSet = (end - start +1) %5 == 0 ? 0 :1;
        int[]medianArr = new int[(end-start+1)/5 + offSet];
        //为medianArr赋值。每个值都是连续5个的中位数
        for (int i = 0; i < medianArr.length; i++) {
            int startI = 5*i+start;
            int endI = startI + 5 <= end ? startI+5 : end;
            medianArr[i] = getMedian(arr,startI,endI);
        }
        //返回medianArr的中位数
        return getMedian(medianArr,0,medianArr.length-1);
    }

    //获取中位数
    private static int getMedian(int[] arr, int start, int end) {
        //快排
        Arrays.sort(arr);
//        insertSort(arr,start,end);
        //偶数个就是前一个
        return arr[start + (end-start)/2];
    }

    private static void insertSort(int []arr, int start ,int end){
        for (int i = start + 1; i <= end ; i++) {
            for (int j = i; j > start && arr[j-1] > arr[j] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        ArrayList<Integer> list = getMinK1(arr, 4);
        list.forEach(System.out::println);
        list = getMinK2(arr,8);
        list.forEach(System.out::println);
    }
}
